package top.likeqc.leetcode.editor.cn;

/**
 * @see <a href="https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor">1026.
 *     节点与其祖先之间的最大差值</a>
 */
public class MaximumDifferenceBetweenNodeAndAncestor {
    public static void main(String[] args) {
        Solution solution = new MaximumDifferenceBetweenNodeAndAncestor().new Solution();
    }
    // leetcode submit region begin(Prohibit modification and deletion)
    /**
     * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode
     * right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left,
     * TreeNode right) { this.val = val; this.left = left; this.right = right; } }
     */
    class Solution {
        public int maxAncestorDiff(TreeNode root) {
            return dfs(root, root.val, root.val);
        }

        public int dfs(TreeNode root, int min, int max) {
            if (root == null) {
                return 0;
            }

            int diff = Math.max(Math.abs(root.val - min), Math.abs(root.val - max));

            min = Math.min(min, root.val);
            max = Math.max(max, root.val);
            diff = Math.max(diff, dfs(root.left, min, max));
            diff = Math.max(diff, dfs(root.right, min, max));
            return diff;
        }
    }
    // leetcode submit region end(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
